/*
 * Copyright (C) 2008 by The Regents of the University of California
 * Redistribution of this file is permitted under the terms of the GNU
 * Public License (GPL).
 *
 * @author Junghoo "John" Cho <cho AT cs.ucla.edu>
 * @date 3/24/2008
 */
 
#include "BTreeIndex.h"
#include "BTreeNode.h"

using namespace std;

/*
 * BTreeIndex constructor
 */
BTreeIndex::BTreeIndex()
{
    rootPid = -1;
    treeHeight = 0;
    treeCursor = 0;
    pushKey = -1;
}

/*
 * Open the index file in read or write mode.
 * Under 'w' mode, the index file should be created if it does not exist.
 * @param indexname[IN] the name of the index file
 * @param mode[IN] 'r' for read, 'w' for write
 * @return error code. 0 if no error
 */
RC BTreeIndex::open(const string& indexname, char mode)
{
  return pf.open(indexname + ".idx", mode);
}

/*
 * Close the index file.
 * @return error code. 0 if no error
 */
RC BTreeIndex::close()
{
  return pf.close();
}

/*
 * Insert (key, RecordId) pair to the index.
 * @param key[IN] the key for the value inserted into the index
 * @param rid[IN] the RecordId for the record being inserted into the index
 * @return error code. 0 if no error
 */
RC BTreeIndex::insert(int key, const RecordId& rid)
{
  RC rc;
  BTNonLeafNode bNode;
  BTLeafNode bLeaf;
  
  /////////////////////////
  // Initializing a tree //
  /////////////////////////
  if (rootPid < 0)
  {
    rootPid = 0;
    bNode.initializeRoot(1, key, 2);
    if (bLeaf.write(1, pf) < 0) // Empty node
    { return RC_FILE_WRITE_FAILED; }
    bLeaf.insert(key, rid);
    bLeaf.setNextNodePtr(-1);
    if (bNode.write(rootPid, pf) < 0)
    { return RC_FILE_WRITE_FAILED; }
    if (bLeaf.write(2, pf) < 0)
    { return RC_FILE_WRITE_FAILED; }
    treeHeight = 2; // Root level + Leaf level
    treeCursor = 1; // Set cursor to point at Root level
    pidCount = 1; // Starts at zero
    return 0;
  }

  PageId pid = rootPid;
  PageId pidTemp = rootPid;

  for(int i = 0; i < treeCursor; i++)
  {
    // Read the page from the PageFile; if a leaf node, then loop terminates
    pid = pidTemp;
    if(treeCursor == treeHeight && i+1 == treeCursor)
    {
      if (bLeaf.read(pid, pf) < 0)
      { return RC_FILE_READ_FAILED; } 
    }
    else
    { 
      if (bNode.read(pid, pf) < 0)
      { return RC_FILE_READ_FAILED; }
    } 
    // Find the child, and follow the "pointer" 
    if (bNode.locateChildPtr(key, pidTemp) < 0)
    { return RC_INVALID_ATTRIBUTE; }                                                
  }
  
  
  /////////////////////
  // Leaf node level //
  /////////////////////
  if(treeCursor == treeHeight)
  { 
    if (bLeaf.insert(key, rid) < 0) // If node is full
    {
      BTLeafNode sib;
      int sibKey;
      bLeaf.insertAndSplit(key, rid, sib, sibKey);
      
      pushKey = sibKey; // Set pushKey to sibling's first key value
      
      pidCount++; // Increment pid count
      PageId sibPid = bLeaf.getNextNodePtr();
      sib.setNextNodePtr(sibPid); // Set sibling's next node pointer value to point to the node the current node is pointing at
      bLeaf.setNextNodePtr(pidCount); // Set current nodes' next node pointer value to point to the sibling node
      if (sib.write(pidCount, pf) < 0) // Write sibling node back to disk
      { return RC_FILE_WRITE_FAILED; } 
    }     
    
    if (bLeaf.write(pid, pf) < 0) // Write node back to disk
    { return RC_FILE_WRITE_FAILED; }
    treeCursor--;    
     
    return 0;  
  }
  
  /////////////////////////
  // Non-leaf node level //
  /////////////////////////

  treeCursor++; // Increment treeCursor to point to next level for next call on insert
  
  insert(key, rid); // Recursive call
  
  if (pushKey >= 0) // If we need to update the node at this level because the child level overflowed
  {
    if (bNode.insert(key, pid) < 0) // If node is full
    {
      BTNonLeafNode sib;
      int sibKey;
      bNode.insertAndSplit(key, pid, sib, sibKey);
      
      pushKey = sibKey; // Set pushKey to sibling's first key value
      
      pidCount++; // Increment pid count
      PageId sibId = pidCount; // Set sibling's pid to current max pid
      
      if (treeCursor == 1) // If it was the root node that overflowed 
      {
        BTNonLeafNode bRoot;
        bRoot.initializeRoot(pid, pushKey, sibId);
        treeHeight++;
        pidCount++;
        if (bRoot.write(pidCount, pf) < 0) // Write root node back to disk
        { return RC_FILE_WRITE_FAILED; }       
      }
      
      if (sib.write(sibId, pf) < 0) // Write sibling node back to disk
      { return RC_FILE_WRITE_FAILED; } 
    }
    else
     { pushKey = -1; }     
    
    if (bNode.write(pid, pf) < 0) // Write node back to disk
    { return RC_FILE_WRITE_FAILED; }
    
    if (treeCursor != 1)
    { treeCursor--; } // decrement treeCursor to point to previous tree level for calling function
    
    return 0;  
  }
}

/*
 * Find the leaf-node index entry whose key value is larger than or 
 * equal to searchKey, and output the location of the entry in IndexCursor.
 * IndexCursor is a "pointer" to a B+tree leaf-node entry consisting of
 * the PageId of the node and the SlotID of the index entry.
 * Note that, for range queries, we need to scan the B+tree leaf nodes.
 * For example, if the query is "key > 1000", we should scan the leaf
 * nodes starting with the key value 1000. For this reason,
 * it is better to return the location of the leaf node entry 
 * for a given searchKey, instead of returning the RecordId
 * associated with the searchKey directly.
 * Once the location of the index entry is identified and returned 
 * from this function, you should call readForward() to retrieve the
 * actual (key, rid) pair from the index.
 * @param key[IN] the key to find.
 * @param cursor[OUT] the cursor pointing to the first index entry
 *                    with the key value.
 * @return error code. 0 if no error.
 */
RC BTreeIndex::locate(int searchKey, IndexCursor& cursor)
{
  BTNonLeafNode bNode;
  BTLeafNode bLeaf;
  PageId pid = rootPid;
  PageId pidTemp = rootPid;

  for(int i = 0; i < treeHeight; i++)
  {
    // Read the page from the PageFile; if a leaf node, then loop terminates
    pid = pidTemp;
    if(i+1 == treeHeight)
    {
      if (bLeaf.read(pid, pf) < 0)
      { return RC_FILE_READ_FAILED; } 
    }
    else
    { 
      if (bNode.read(pid, pf) < 0)
      { return RC_FILE_READ_FAILED; }
    } 
    // Find the child, and follow the "pointer" 
    if (bNode.locateChildPtr(searchKey, pidTemp) < 0)
    { return RC_INVALID_ATTRIBUTE; }                                                
  }
  
  int eid;
  bLeaf.locate(searchKey, eid);
  cursor.pid = pid;
  cursor.eid = eid;

  return 0;
}

/*
 * Read the (key, rid) pair at the location specified by the index cursor,
 * and move foward the cursor to the next entry.
 * @param cursor[IN/OUT] the cursor pointing to a leaf-node index entry in the b+tree
 * @param key[OUT] the key stored at the index cursor location.
 * @param rid[OUT] the RecordId stored at the index cursor location.
 * @return error code. 0 if no error
 */
RC BTreeIndex::readForward(IndexCursor& cursor, int& key, RecordId& rid)
{
  /* Store values of the cursor */
  int pid = cursor.pid;
  int eid = cursor.eid;

  /* Initialize local leaf node */
  BTLeafNode bLeaf;

  /* Read appropriate leaf node */
  if (bLeaf.read(pid, pf) < 0) {
    return RC_FILE_READ_FAILED;
  }

  /* Obtain key, rid pair */
  bLeaf.readEntry(eid, key, rid);

  /* Move cursor to next entry */
  /// 3 cases
  /// 1. next entry is in the same node (same pid, next eid)
  /// 2. node is not full, but next entry does not exist
  /// 3. node is full, so next entry is in the next node (getNextNodePtr,0)
  /// 4. next node does not exist

  /* Case 1 */
  if(eid < 84) {
    /* Case 2
     * If we're at the last record, then error - cannot move forward! */
    if(bLeaf.getKeyCount() == eid+1) {
      return RC_INVALID_CURSOR;
    }
    /* Otherwise, go to the next record in the node */
    else {
      cursor.eid++;
    }
  }

  /* Case 3 */
  else if(eid == 84) {
    /* Case 4
     * If we're at the last node, then error - cannot move forward! */
    if(cursor.pid == -1) {
      return RC_INVALID_CURSOR;
    }
    /* Otherwise, go to the next node, starting with eid 0 */
    else {
      cursor.pid = bLeaf.getNextNodePtr();
      cursor.eid = 0;
    }
  }

  return 0;
}











